import functools
from typing import List


class Solution:
    def minimumMoves(self, arr: List[int]) -> int:
        return self.solve(tuple(arr)) + 1

    @functools.lru_cache(None)
    def solve(self, s):
        """通过多少次删除可以让s变成一个回文字符串"""
        if len(s) == 0 or len(s) == 1:
            return 0

        ans = 1 + self.solve(s[:-1])

        for i in range(len(s) - 1):
            if s[i] == s[-1]:
                if i != 0:
                    ans = min(ans, (1 + self.solve(tuple(s[:i]))) + self.solve(tuple(s[i + 1:-1])))
                else:
                    ans = min(ans, self.solve(tuple(s[1:-1])))
        return ans


if __name__ == "__main__":
    print(Solution().minimumMoves([1, 2]))  # 2
    print(Solution().minimumMoves([1, 3, 4, 1, 5]))  # 3
